package algorithms.leecode;

import java.util.ArrayList;
import java.util.List;

public class Au60 {
    public static void main(String[] args) {
        System.err.println(new Au60().getPermutation(4,9));
    }
    public String getPermutation(int n, int k) {
        char[] arr = new char[n];

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i + 1);
        }
        for (int i = 0; i < n; i++) {
            int cut = getplus(n - i - 1);
            int start = 0;
            // 计算第几队列
            if (cut != 0) {
                start = k / cut;
                int less = k % cut;
                if (less == 0) {
                    start--;
                }
            }

            int x = list.get(start);
            arr[i] =  (char) (x+'0');
            if (start != 0) {
                k -= cut * start ;
            }

            list.remove(start);
        }

        return new String(arr);

    }

    public int getplus(int n) {
        int res = n;
        if (n > 1) {
            res *= getplus(n - 1);
        }
        return res;
    }
}
